package tree.ordertraversal;

import tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Classname : ConstructBinaryTreeFromInorderAndPostorderTraversal
 * @Description :
 * <a href="https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/">106. 从中序与后序遍历序列构造二叉树</a>
 * @Author : chentianyu
 * @Date 2023/1/23 15:51
 */


public class ConstructBinaryTreeFromInorderAndPostorderTraversal {

    /**
     * 思路：后序遍历用于重建树，中序遍历辅助区分左右子树（通过获取左子树个数）
     *
     * @param inorder
     * @param postorder
     * @return
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) indexMap.put(inorder[i], i);

        return buildTreeHelper(postorder, indexMap, 0, postorder.length - 1, 0);
    }

    private TreeNode buildTreeHelper(int[] postorder, Map<Integer, Integer> indexMap, int postStart, int postEnd, int inStart) {
        if (postStart > postEnd) return null;

        TreeNode root = new TreeNode(postorder[postEnd]);
        int index = indexMap.get(postorder[postEnd]);
        int leftSize = index - inStart;
        root.left = buildTreeHelper(postorder, indexMap, postStart, postStart + leftSize - 1, inStart);
        root.right = buildTreeHelper(postorder, indexMap, postStart + leftSize, postEnd - 1, index + 1);
        return root;
    }
}
